import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.FileReader;
import java.io.FileWriter;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
import java.util.TreeSet;
//gggg
//gghhjjhn
//bleeee
//netbean
public class Search {

    public static void main(String[] args) {
        if (args.length == 2) {
            String inFile = args[0];
            String outFile = args[1];
            //String inFile = "C:/mohom2.txt";
            DoSearch search = new DoSearch(new InputParser(inFile));
            search.Run();
            String result = search.result();
            try {
                FileWriter fstream = new FileWriter(outFile);
                BufferedWriter out = new BufferedWriter(fstream);
                out.write(result);
                out.close();
            } catch (Exception e) {
                System.out.println("Error: " + e.getMessage());
            }
        }

      
    }
}

class InputParser {
    int state;
    List<Point> v, EndPoints; 
    private Point StartPoint;
    int heuristics, method;
    
    Point t;
    public InputParser(String file) {
        String line;
        v=new ArrayList<Point>();
        EndPoints=new ArrayList<Point>();
        try {
            state=0;
            BufferedReader reader = new BufferedReader(new FileReader(file));
            while ((line = reader.readLine()) != null) {
                ParseLine(line);
            }
            reader.close();
        } catch (Exception e) {
            System.out.println(e.getLocalizedMessage());
        }

    }
    private void ParseLine(String l) {
        if (l.length() == 0) return;
        else if (l.charAt(0) == "#".charAt(0)) {
            state++;
            return;
        }
        if (state == 1) stateOne(l);
        else if (state == 2) stateTwo(l);
        else if (state == 3) stateThree(l);
        else if (state == 4) stateFour(l);
        else if (state == 5) heuristics = Integer.parseInt(l);
        else if (state == 6) method = Integer.parseInt(l);
        return;
    }
    private void stateOne(String l) {
            String delimiter = "\t";
            String[] res = l.split(delimiter);
            v.add(new Point(Integer.parseInt(res[0]), res[1], Integer.parseInt(res[2]), Integer.parseInt(res[3])));
    } 
    public void stateTwo(String l) {
                    String delimiter = "\t";
            String[] res = l.split(delimiter);
            Point a = null, b = null;
            int a_id = Integer.parseInt(res[0]), b_id = Integer.parseInt(res[1]);
            int cost = Integer.parseInt(res[2]);
            for (Point p : v) {
                if (p.HasId(a_id)) {
                    a = p;
                } else if (p.HasId(b_id)) {
                    b = p;
                }
            }
            a.AddEdge(new Edge(b, cost));
            b.AddEdge(new Edge(a, cost));
    }
    public void stateThree(String l) {
        int id = Integer.parseInt(l);
            for (Point p : v) {
                if (p.HasId(id)) {
                    StartPoint = p;
                    break;
                }
            }
    }
    private void stateFour(String l) {
            int id = Integer.parseInt(l);
            for (Point p : v) {
                if (p.HasId(id)) {
                    EndPoints.add(p);
                }
            }
    }

    public Point getStartPoint() {
        return StartPoint;
    }
    public List<Point> GetEndPoints() {
        return EndPoints;
    }
    public List<Point> GetPoints() {
        return v;
    }

    int GetHeuristics() {
        return heuristics;
    }
    int GetMethod() {
        return method;
    }
}



interface VertexPrimitive {
    public void AddEdge(Edge e);
    public Boolean HasId(int i);
    public int getId();
    public String getName();
    public int getX();
    public int getY();
    public TreeSet<Edge> getEdges(int asc_desc);
    public Boolean getVisited();
    public void setVisited();
    public void setFrom(Point i);
    public Point getFrom();
    public Point getPoint();
    public void setTC(int c);
    public int getTC();
}

class Point implements VertexPrimitive {
    int id, x,y, total_cost;
    public double temp = 0;
    Boolean visited=false;
    String name;
    //List<Edge> edges;
    TreeSet<Edge> edges_DESC, edges_ASC;
    Point from;
    public Point(int id0, String n, int x0, int y0) {
        id=id0;
        name=n;
        x=x0;
        y=y0;
        total_cost=0;
        //edges=new ArrayList<Edge>();
        edges_DESC=new TreeSet<Edge>();
        edges_ASC=new TreeSet<Edge>(Collections.reverseOrder());
    }
    public Point( Point p) {
        id=p.getId();
        name=p.getName();
        x=p.getX();
        y=p.getY();
        edges_ASC=p.getEdges(0);
        edges_DESC=p.getEdges(1);
    }
    @Override
    public void AddEdge(Edge e) {
       edges_DESC.add(e);
       edges_ASC.add(e);
    }
    @Override
    public Boolean HasId(int i) {return i==id;}
    @Override
    public int getId() {return id;}
    @Override
    public String getName() { return name;}
    @Override
    public int getX() { return x;}
    @Override
    public int getY() { return y;}
    @Override
    public TreeSet<Edge> getEdges(int asc_desc) { if(asc_desc ==0) return edges_ASC; else return edges_DESC; }
    @Override
    public Boolean getVisited() { return visited; }
    @Override
    public void setVisited() {visited=true;}
    @Override
    public void setFrom(Point i) {from=i;}
    @Override
    public Point getFrom() {return from;}
    @Override
    public Point getPoint() {return this;}
    @Override
    public void setTC(int c) {total_cost=c;}
    @Override
    public int getTC() {return total_cost;}
}

class Edge implements VertexPrimitive,Comparable {
    Point pp;
    int cost;
    public Edge(Point p, int c) {
        pp=p;
        cost=c;
    }
    public int C() {
        return cost;
    }
    @Override
    public void AddEdge(Edge e) {
       pp.AddEdge(e);
    }
    @Override
    public Boolean HasId(int i) {return pp.HasId(i);}
    @Override
    public int getId() {return pp.getId();}
    @Override
    public String getName() { return pp.getName();}
    @Override
    public int getX() { return pp.getX();}
    @Override
    public int getY() { return pp.getY();}
    @Override
    public TreeSet<Edge> getEdges(int i) { return pp.getEdges(i); }
    @Override
    public Boolean getVisited() { return pp.getVisited(); }
    @Override
    public void setVisited() {pp.setVisited();}
    @Override
    public void setFrom(Point i) {pp.setFrom(i);}
    @Override
    public Point getFrom() {return pp.getFrom();}
    @Override
    public Point getPoint() {return pp;}
    @Override
    public void setTC(int c) {pp.setTC(c);}
    @Override
    public int getTC() {return pp.getTC();}
    @Override
    public int compareTo(Object o) {
        if(getId() > ((VertexPrimitive) o).getId() ) {
            return -1;
        }
        if(getId() < ((VertexPrimitive) o).getId() ) {
            return 1;
        }
        return 0;
    }
}


class DoSearch {
    Point StartPoint;
    List<Point> EndPoints, Points;
    Heuristics h;
    SearchType st;
    public DoSearch(InputParser p) {
        StartPoint = p.getStartPoint();
        EndPoints = p.GetEndPoints();
        Points = p.GetPoints();
        int i=p.GetHeuristics();
        if(i==1) h=new Konstans0();
        else if(i==2) h=new Manhattan();
        else if(i==3) h=new Legvonal();
        i=p.GetMethod();
        if(i==1) st=new BFS();
        else if(i==2) st=new DFS();
        else if(i==3) st=new Egyenletes();
        else if(i==4) st=new Moho();
        else if(i==5) st=new Acsillag();
    }
    public void Run() {
        st.run(StartPoint, EndPoints, Points, h);
    }
    public String result() {
        return st.result();
    }
}

interface Heuristics {
 public double h(Point p1, List<Point> end);
}
class Konstans0 implements Heuristics {
    @Override
    public double h(Point p1, List<Point> end) {
        return 0.0;
    } 
}
class Manhattan implements Heuristics {
    List<Double> res;
    public Manhattan() {
        res=new ArrayList<Double>();
    }
    @Override
    public double h(Point p1, List<Point> end) {
        double ret;
        for(Point p2:end)
            res.add( (double)(Math.abs(p1.getX()-p2.getX()) + Math.abs(p1.getY()-p2.getY())) );
        Collections.sort(res);
        ret= res.get(0);
        res.clear();
        return ret;
    } 
}
class Legvonal implements Heuristics {
    List<Double> res;
    public Legvonal() {
        res=new ArrayList<Double>();
    }
    @Override
    public double h(Point p1, List<Point> end) {
        double ret;
        for(Point p2:end)
            res.add( Math.sqrt((double)((p1.getX()-p2.getX())*(p1.getX()-p2.getX()) + (p1.getY()-p2.getY())*(p1.getY()-p2.getY())) ));
        Collections.sort(res);
        ret = res.get(0);
        res.clear();
        return ret;
    } 
}

class SearchType {
    protected Point ept;
    protected Comparator VertexComparator = new Comparator<VertexPrimitive>() {
            @Override
            public int compare(VertexPrimitive o1, VertexPrimitive o2) {
                return (o2.getId()-o1.getId())*(-1);
            }
        };
    public void run(VertexPrimitive start, List<Point> end, List<Point> points, Heuristics h) {}
    public String result() {
        Point tmp;
        List<Integer> result=new ArrayList<Integer>();
        tmp=ept;
        while( tmp !=null && tmp.getId() > 0) {
            result.add(tmp.getId());
            tmp=tmp.getFrom();
        }
        String res="";
        for(int j=result.size()-1; j >= 0; j--) {
            res = res+result.get(j).toString();
            if(j!=0) res = res + "\r\n";
        }
        return res;
    }   
}

class BFS extends SearchType {
    List<VertexPrimitive> OpenList, CloseList;
    Boolean stop = false;
    public BFS() {
        OpenList=new ArrayList<VertexPrimitive>();
        CloseList=new ArrayList<VertexPrimitive>();
    }
    @Override
    public void run(VertexPrimitive start, List<Point> end, List<Point> points, Heuristics h) {
        OpenList.add(start);
        start.setVisited();
        while(!stop && !OpenList.isEmpty() ) {
            extract(OpenList.get(0), end);
        }
    }
    private void extract(VertexPrimitive p, List<Point> end) {
        for(Point v:end)
            if(p.getId() == v.getId()) {stop=true; ept=p.getPoint(); return; }
        for(Edge e : p.getEdges(0)) {
            if(!e.getVisited()) {
                OpenList.add(e);
                e.setVisited();
                e.setFrom(p.getPoint());
            }
            }
        
        OpenList.remove(p);
        CloseList.add(p);
    }
    
}
class DFS extends SearchType {
    List<VertexPrimitive> OpenList, CloseList;
    Boolean stop = false, first=true;
    public DFS() {
        OpenList=new ArrayList<VertexPrimitive>();
        CloseList=new ArrayList<VertexPrimitive>();
    }
    @Override
    public void run(VertexPrimitive start, List<Point> end, List<Point> points, Heuristics h) {
        if(stop) return;
        for(Point v:end)
            if(start.getId() == v.getId()) {stop=true; ept=start.getPoint(); return; }
        if(first) {OpenList.add(start);first=false;start.setVisited();}
        for(Edge e: start.getEdges(1)) {
            if(!e.getVisited()) {
                e.setVisited();
                e.setFrom(start.getPoint());
                OpenList.add(e);
            }
        }
        OpenList.remove(start);
        CloseList.add(start);
        if(!OpenList.isEmpty()) run( OpenList.get(OpenList.size()-1) , end, points, h);
    }
}
class Egyenletes extends SearchType {
    List<VertexPrimitive> OpenList, CloseList;
    Boolean stop = false, first=true;
    public Egyenletes() {
        OpenList=new ArrayList<VertexPrimitive>();
        CloseList=new ArrayList<VertexPrimitive>();
    }
    @Override
    public void run(VertexPrimitive start, List<Point> end, List<Point> points, Heuristics h) {
        if(stop) return;
        for(Point v:end)
            if(start.getId() == v.getId()) {stop=true; ept=start.getPoint(); return; }
        if(first) {OpenList.add(start);first=false;start.setVisited();}
        for(Edge e: start.getEdges(0)) {
            if(!e.getVisited()) {
                e.setVisited();
                e.setFrom(start.getPoint());
                e.setTC(start.getTC()+e.C());
                OpenList.add(e);
            }
        }
        OpenList.remove(start);
        CloseList.add(start);
        if(!OpenList.isEmpty()) run( getMin() , end, points, h);
    }
    private VertexPrimitive getMin() {
        int min=100000;
        List<VertexPrimitive> mins = new ArrayList<VertexPrimitive>();
        for(VertexPrimitive p: OpenList) {
            if( ((Edge)p).getTC() < min ) {
                min=((Edge)p).getTC();
                mins.clear();
                mins.add(p);
            }
            else if(((Edge)p).getTC() == min) mins.add(p);
        }
        Collections.sort(mins, VertexComparator);
        return mins.get(0);
    }

}
class Moho extends SearchType {
    List<VertexPrimitive> OpenList, CloseList;
    Boolean stop = false, first=true;
    public Moho() {
        OpenList=new ArrayList<VertexPrimitive>();
        CloseList=new ArrayList<VertexPrimitive>();
    }
    @Override
    public void run(VertexPrimitive start, List<Point> end, List<Point> points, Heuristics h) {
        if(stop) return;
        for(Point v:end)
            if(start.getId() == v.getId()) {stop=true; ept=start.getPoint(); return; }
        if(first) {OpenList.add(start);first=false;start.setVisited();}
        for(Edge e: start.getEdges(0)) {
            if(!e.getVisited()) {
                e.setVisited();
                e.setFrom(start.getPoint());
                OpenList.add(e);
            }
        }
        OpenList.remove(start);
        CloseList.add(start);
        if(!OpenList.isEmpty()) run( getMin(h, end) , end, points, h);
    }
    private VertexPrimitive getMin(Heuristics h, List<Point> end) {
        double min=100000;
        List<VertexPrimitive> mins = new ArrayList<VertexPrimitive>();
        VertexPrimitive m=null;
        for(VertexPrimitive p: OpenList) {
            if( h.h(p.getPoint(), end) < min ) {
                min=h.h(p.getPoint(), end);
                mins.clear();
                mins.add(p);
            }
            else if(h.h(p.getPoint(), end) == min) mins.add(p);
        }
        Collections.sort(mins, VertexComparator);
        return mins.get(0);
    }

}
class Acsillag extends SearchType {
    List<VertexPrimitive> OpenList, CloseList;
    Boolean stop = false, first=true;
    public Acsillag() {
        OpenList=new ArrayList<VertexPrimitive>();
        CloseList=new ArrayList<VertexPrimitive>();
    }
    @Override
    public void run(VertexPrimitive start, List<Point> end, List<Point> points, Heuristics h) {
        if(stop) return;
        for(Point v:end)
            if(start.getId() == v.getId()) {stop=true; ept=start.getPoint(); return; }
        if(first) {OpenList.add(start);first=false;start.setVisited();}
        for(Edge e: start.getEdges(0)) {
            if(!e.getVisited()) {
                e.setVisited();
                e.setFrom(start.getPoint());
                e.setTC(e.C() + start.getTC());
                e.getPoint().temp=h.h(e.getPoint(), end) + ((double)e.getTC());
                OpenList.add(e);
            }
        }
        OpenList.remove(start);
        CloseList.add(start);
        Collections.sort(OpenList, new Comparator<VertexPrimitive>() 
        {
            @Override
            public int compare(VertexPrimitive o1, VertexPrimitive o2) {
                return (o2.getId()-o1.getId())*(-1);
            }
        }
         );
        if(!OpenList.isEmpty()) run( getMin(h, end) , end, points, h);
    }
    private VertexPrimitive getMin(Heuristics h, List<Point> end) {
        double min=100000;
        List<VertexPrimitive> mins = new ArrayList<VertexPrimitive>();
        for(VertexPrimitive p: OpenList) {
            if( h.h(p.getPoint(), end)+((double)p.getTC()) < min ) {
                min=h.h(p.getPoint(), end)+((double)p.getTC());
                mins.clear();
                mins.add(p);
            }
        }
        Collections.sort(mins, VertexComparator);
        return mins.get(0);
    }

}
